Exercise: Random Binary Search Trees - Data Structures with Generic Types in Python

Task#

Design and implement an algorithm that constructs a Treap from a sorted array, a, of n elements. This method should run in $O(n)$ worst-case time and should construct a Treap that is indistinguishable from one in which the elements of a were added one at a time using the add(x) method.

Sample input

The sample input will be as follows:

Expected output

The expected output will be as follows:

Tree contents:
1 2 3 4 5 6 
Tree contents after removing 4:
1 2 3 5 6

main.py

arrayqueue.py

binarytree.py

base.py

utils.py

binarysearchtree.py

import random
from binarysearchtree import BinarySearchTree
# Main class
class Treap(BinarySearchTree):
    class Node(BinarySearchTree.Node):
        def __init__(self, x):
            super(Treap.Node, self).__init__(x)
            self.p = random.random()
            
        def __str__(self):
            return "[%r,%f]" % (self.x, self.p)
    # Initialize function    
    def __init__(self, iterable=[]):
        super(Treap, self).__init__(iterable)
    # Function to create new node
    def _new_node(self, x):
        return Treap.Node(x)
    # Function to add all values 
    def addall(self, a):
        # Write code here
        pass
    # Function to add all values recursively
    def addallrecursive(self, a, low, high, p):
        # Write code here
        pass
    # Function to bubble up treap        
    def bubble_up(self, u):
        while u != self.r and u.parent.p > u.p:
            if u.parent.right == u:
                self.rotate_left(u.parent)
            else:

Enter to Rename, Shift+Enter to Preview

Task to implement addall() and addallrecursive() method